class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> submit = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(1,n,k);
        return res;
    }

    private void dfs(int cur,int n,int k) {

        //剪枝 如果submit.size() 和 n-cur 的和 小于 k 就不需要继续往下走了,不可能还有k个值
        if(submit.size() +(n-cur+1) < k) {
            return;
        }
        if(submit.size() == k) {
            res.add(new ArrayList<>(submit));
            return;
        }
        submit.add(cur);
        dfs(cur+1,n,k);
        submit.remove(submit.size()-1);
        dfs(cur+1,n,k);
    }
}